//根据一个有序数组构造一个平衡搜索二叉树
//只需像二分一样，每次都选择中间的树来作为根节点来构造就可以了
#include<vector>
using std::vector;
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};
//递归法
TreeNode* traversal(vector<int>& nums,int left,int right){
    if(left>right) return nullptr;
    int mid=left+(right-left)/2;
    TreeNode* root=new TreeNode(nums[mid]); //全程左闭右闭区间

    root->left=traversal(nums,left,mid-1);          //左区间-左子树
    root->right=traversal(nums,mid+1,right);        //右区间-右子树
    return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
    if(!nums.size()) return nullptr;
    return traversal(nums,0,nums.size()-1);
}


//迭代法
//使用三个队列存储节点、左区间边界、右区间边界。并保持同出同进
#include <queue>
using std::queue;
TreeNode* sortedArrayToBST(vector<int>& nums) {
    if(!nums.size()) return nullptr;
    
    TreeNode* root=new TreeNode(nums[(nums.size())/2]);
    queue<int> que_left;
    queue<int> que_right;
    queue<TreeNode*> que_node;
    que_left.push(0);
    que_right.push(nums.size()-1);
    que_node.push(root);
    while(!que_node.empty()){
        int left=que_left.front(); que_left.pop();
        int right=que_right.front(); que_right.pop();
        TreeNode* cur=que_node.front(); que_node.pop();
        int mid=left+(right-left)/2;
        cur->val=nums[mid];


        //左子树
        if(left<=mid-1){
            que_left.push(left);
            que_right.push(mid-1);
            cur->left=new TreeNode(0);
            que_node.push(cur->left);
        }
        //右子树
        if(right>=mid+1){
            que_left.push(mid+1);
            que_right.push(right);
            cur->right=new TreeNode(0);
            que_node.push(cur->right);
        }

    }

    return root;
}